package site.wanjiahao.sort.compare;

import site.wanjiahao.sort.Sort;

public class HeapSort<E extends Comparable<E>> extends Sort<E> {

    private int size;

    /**
     * 挑出最大的家伙，可以使用二叉堆来实现
     */
    @Override
    protected void sort() {
        // 原地建堆
        heapify();
        // 数组首部是最大元素
        while (size > 1) {
            // 交换数组头部和尾部数据，并且剔除尾部数据
            swap(0, --size);
            // 下滤数据
            siftDown(0);
        }
    }

    private void heapify() {
        size = array.length;
        // 自下而上的下滤(O(n)) 自上而下的上滤，相当于添加(O(nlogn))
        for (int i = size - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    // 下滤
    private void siftDown(int index) {
        E cur = array[index];
        int cIndex;
        boolean swap = false;
        while ((cIndex = (index << 1) + 1) < size) {
            int rIndex = cIndex + 1;
            // 找出左右节点最大值
            if (rIndex < size) {
                // 存在右节点
                cIndex = cmp(array[cIndex], array[rIndex]) > 0 ? cIndex : rIndex;
            }
            if (cmp(cur, array[cIndex]) > 0) break;
            // 交换元素
            array[index] = array[cIndex];
            index = cIndex;
            swap = true;
        }
        if (swap) array[index] = cur;
    }
}
